package DecChallenges;

import java.util.Arrays;

public class Day15_P1155 {
    public static int MOD = (int)1e9 + 7;
    public static void main(String[] args) {
        test();
    }

    public static int dp(int k, int target, int rest, int[][] memo) {
        if(rest == 1) return target <= k ? 1 : 0;
        if(memo[target][rest] != -1) return memo[target][rest];
        int res = 0;
        for(int i = 1; i <= Math.min(k, target - (rest - 1)); i++) {
            if(memo[target - i][rest - 1] == - 1) {
                memo[target - i][rest - 1] = dp(k, target - i, rest - 1, memo);
            }
            res = (res + memo[target - i][rest - 1]) % MOD;
        }
        memo[target][rest] = res % MOD;
        return memo[target][rest];
    }
    public static int numRollsToTarget(int n, int k, int target) {
        int[][] memo = new int[target + 1][n + 1];
        for(int[] t: memo) Arrays.fill(t, -1);
        return dp(k, target, n, memo);
    }

    public static int brute(int k, int target, int rest) {
        if(rest == 1) return target <= k ? 1 : 0;
        int res = 0;
        for(int i = 1; i <= Math.min(k, target - (rest - 1)); i++) {
            res = (res + brute(k, target - i, rest - 1)) % MOD;
        }
        return res % MOD;
    }
    public static int numRollsToTargetBrute(int n, int k, int target) {
        return brute(k, target, n);
    }

    public static void test() {
        int n = 10;
        int k = 10;
        int target = 40;
        long s,e;
        s = System.currentTimeMillis();
        System.out.println(numRollsToTarget(n, k, target));
        e = System.currentTimeMillis();
        System.out.println("Smart method:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        System.out.println(numRollsToTargetBrute(n, k, target));
        e = System.currentTimeMillis();
        System.out.println("Stupid method:" + (e - s) + "ms");
    }
}
